

//给你一个下标从 0 开始的二维整数数组 tires ，其中 tires[i] = [fi, ri] 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 
//fi * ri⁽ˣ⁻¹⁾ 秒。 
//
// 
// 比方说，如果 fi = 3 且 ri = 2 ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 1 圈赛道耗时 3 秒，完成第 2 圈耗时 3 * 2 
//= 6 秒，完成第 3 圈耗时 3 * 2² = 12 秒，依次类推。 
// 
//
// 同时给你一个整数 changeTime 和一个整数 numLaps 。 
//
// 比赛总共包含 numLaps 圈，你可以选择 任意 一种轮胎开始比赛。每一种轮胎都有 无数条 。每一圈后，你可以选择耗费 changeTime 秒 换成 
//任意一种轮胎（也可以换成当前种类的新轮胎）。 
//
// 请你返回完成比赛需要耗费的 最少 时间。 
//
// 
//
// 示例 1： 
//
// 输入：tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
//输出：21
//解释：
//第 1 圈：使用轮胎 0 ，耗时 2 秒。
//第 2 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
//第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。
//第 4 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
//总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。
//完成比赛的最少时间为 21 秒。
// 
//
// 示例 2： 
//
// 输入：tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
//输出：25
//解释：
//第 1 圈：使用轮胎 1 ，耗时 2 秒。
//第 2 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
//第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。
//第 4 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
//第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。
//总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。
//完成比赛的最少时间为 25 秒。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= tires.length <= 10⁵ 
// tires[i].length == 2 
// 1 <= fi, changeTime <= 10⁵ 
// 2 <= ri <= 10⁵ 
// 1 <= numLaps <= 1000 
// 
// 👍 32 👎 0


package cn.db117.leetcode.solution21;

import java.util.Arrays;

/**
 * 2188.完成比赛的最少时间.minimum-time-to-finish-the-race
 *
 * @author db117
 * @since 2022-02-28 15:15:51
 **/

public class Solution_2188 {
    public static void main(String[] args) {
        Solution solution = new Solution_2188().new Solution();
//        System.out.println(solution.minimumFinishTime(new int[][]{{2, 3}, {3, 4}}, 5, 4));
//        System.out.println(solution.minimumFinishTime(new int[][]{{1, 10}, {2, 2}, {3, 4}}, 6, 5));
        // 215088
        System.out.println(solution.minimumFinishTime(new int[][]{{45, 23}, {404, 3}, {735, 24}, {856, 3}, {249, 11},
                {326, 7}, {589, 8}, {91, 17}, {126, 24}, {713, 21}, {606, 13}, {585, 5}, {861, 30}, {604, 4}, {822, 27},
                {231, 6}, {507, 6}, {265, 5}, {912, 12}, {878, 29}, {46, 6}, {421, 20}, {941, 26}, {151, 25}, {490, 4}, {315, 14}, {630, 16},
                {292, 24}, {214, 2}, {432, 18}, {520, 21}, {88, 26}, {4, 21}, {337, 28}, {780, 9}, {220, 29}, {721, 13}, {927, 25}, {67, 25},
                {835, 21}, {646, 19}, {973, 26}, {235, 12}, {427, 9}, {471, 21}, {267, 16}, {388, 8}, {788, 13}, {937, 27}, {810, 26}, {288, 5},
                {966, 28}, {698, 15}, {343, 12}, {648, 20}, {238, 4}, {436, 15}, {588, 4}, {373, 15}, {100, 12}, {180, 19}, {904, 15}, {854, 21},
                {107, 2}, {822, 12}, {485, 24}, {196, 10}, {978, 24}, {178, 10}, {642, 29}, {455, 16}, {490, 17}, {455, 25}, {77, 7}, {456, 15},
                {102, 25}, {767, 19}, {169, 5}, {461, 11}, {385, 25}, {896, 5}, {185, 26}, {885, 14}, {948, 26}, {907, 6}, {877, 18}, {421, 24},
                {783, 15}, {999, 20}, {756, 10}, {308, 12}, {34, 12}, {339, 17}, {613, 15}, {270, 10}, {681, 3}, {385, 15}, {123, 4}, {10, 20},
                {799, 28}, {506, 23}, {265, 24}, {193, 4}, {638, 23}, {144, 29}, {874, 19}, {470, 14}, {195, 16}, {77, 23}, {573, 28}, {559, 12},
                {146, 10}, {538, 10}, {705, 4}, {592, 26}, {258, 24}, {900, 25}, {836, 8}, {353, 5}, {197, 26}, {572, 21}, {347, 17}, {763, 21},
                {67, 20}, {927, 6}, {135, 4}, {392, 30}, {131, 15}, {650, 23}, {100, 30}, {848, 9}, {858, 27}, {203, 15}, {249, 4}, {884, 15},
                {465, 18}, {316, 30}, {730, 15}, {310, 19}, {823, 21}, {785, 21}, {15, 16}}, 772, 502));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
            // 在某轮中一直用一个轮胎跑的最小值
            // 一个轮胎不可能一直跑,需要换胎,一个轮胎最多可以跑 17 次
            long[] min = new long[17];
            Arrays.fill(min, Integer.MAX_VALUE);
            for (int[] tire : tires) {
                long sum = 0;
                long time = tire[0];// 当前次数需要时间
                for (int i = 0; i < Math.min(17, numLaps) && time < changeTime + tire[0]; i++) {
                    sum += time;
                    min[i] = Math.min(min[i], sum);
                    time *= tire[1];
                }
            }

            // 动态规划
            long[] dp = new long[numLaps + 1];

            for (int i = 1; i <= numLaps; i++) {
                dp[i] = Integer.MAX_VALUE;
                for (int j = 0; j < 17 && j < i; j++) {
                    // 前面的已经算完了,后面就算一个轮胎跑完的
                    dp[i] = Math.min(dp[i], dp[i - j - 1] + min[j]);
                    // 需要换轮胎
                }
                dp[i] += changeTime;
            }

            // 第一次不需要换胎,需要减掉
            return (int) dp[numLaps] - changeTime;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}